/*
 * Moseycode
 * Copyright (C) 2008  Tom Gibara
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 * 
 */
package com.tomgibara.mosey.dot;

public class RotaryEncoding {

	public static final int ERROR_NO_GAP = -1;
	public static final int ERROR_NO_DOT = -2;
	public static final int ERROR_NO_MAXIMAL = -3;
	
	public static final int MIN_DOTS = 2;
	public static final int MAX_DOTS = 31;
	
	public static final int[][] FP = new int[MAX_DOTS+1][];
	
	static {
		for (int p = 1; p < MAX_DOTS+1; p++) {
			int[] pfibs = new int[MAX_DOTS+1];
			int s = 0;
			for (int i = 0; i < pfibs.length; i++) {
				int v;
				if (i < p) {
					v = 1 << i;
				} else {
					v = s;
					s -= pfibs[i-p];
				}
				pfibs[i] = v;
				s += v;
			}
			FP[p] = pfibs;
		}
	}

	public final int d;
	private final int[] s;
	
	public RotaryEncoding(int d) {
		if (d > MAX_DOTS) throw new IllegalArgumentException();
		if (d < MIN_DOTS) throw new IllegalArgumentException();
		this.d = d;
		
		s = new int[d-1];
		for (int i = 0; i < s.length; i++) {
			if (i < 3) {
				s[i] = i;
			} else {
				s[i] = s[i-1] + FP[d-i][i-2];
			}
		}
		
	}
	
	public int getMinValue() {
		return 0;
	}
	
	public int getMaxValue() {
		return s[d-2];
	}
	
	public int encode(int v) {
		if (v < 0 || v > s[d-2]) throw new IllegalArgumentException();
		int i;
		for (i = d-2; i >= 0; i--) {
			int u = s[i];
			if (u <= v) {
				v -= u;
				break;
			}
		}
		switch(i) {
		case 0 : return (1 << d)-2;
		case 1 : return (1 << d)-4;
		default:
			int e = (1 << (d-i)) - 2;
			int p = d - i - 1;
			int[] fp = FP[p];
			for (int j = i-2; j >= 0; j--) {
				e <<= 1;
				int u = fp[j];
				if (v >= u) {
					e |= 1;
					v -= u;
				}
			}
			return e << 1;
		}
	}
	
	public int decode(int e, int[] result) {
		int r = orientation(e);
		if (r < 0) return r;
		int p = r >> 16;
		int o = r & 15;
		e = rotateLeft(e, o);
		int[] fp = FP[p];
		int v = 0;
		for (int i = d-p-2; i >= 1; i--) {
			if ((e & (1 << i)) != 0) v += fp[i-1];
		}
		v += s[d - p - 1];
		if (result != null) {
			result[0] = v;
			result[1] = o;
		}
		return v;
	}
	
	private int orientation(int e) {
		int o = Integer.numberOfTrailingZeros( Integer.lowestOneBit(~e) );
		if (o >= d) return ERROR_NO_GAP;
		if (o != 0) e = rotateRight(e, o);
		int s = -1;
		int ml = 0;
		int ms = 0;
		boolean dup = false;
		for (int i = d-1; i >= 0; i--) {
			if ((e & (1<<i)) == 0) {
				if (s != -1) {
					int l = s-i;
					if (l == ml) {
						dup = true;
					} else if (l > ml) {
						ml = l;
						ms = s;
						dup = false;
					}
					s = -1;
				}
			} else {
				if (s == -1) s = i;
			}
		}
		if (ml == 0) return ERROR_NO_DOT;
		if (dup) return ERROR_NO_MAXIMAL;
		o = d-1-ms-o;
		if (o < 0) o += d;
		return (ml << 16) | o;
	}

	private int rotateLeft(int i, int b) {
		return (i << b) | (i >>> (d-b));
	}
	
	private int rotateRight(int i, int b) {
		return (i << d-b) | (i >>> b);
	}
	
}
